package Solution.problem067;

import java.util.ArrayList;
import java.util.List;

/**
 * @program Leetcode
 * @description: 二进制字符串求和，结果也是个二进制字符串
 * 递归，结果用链表保存，然后转换成字符串数据
 * @author: lishangsheng
 * @create: 2019/06/09 14:06
 */
public class Solution {
    public static String addBinary(String a, String b) {
        /** 边界控制*/
        if(a==null||a.equals("")){
            return b;
        }
        if(b==null||b.equals("")){
            return a;
        }
        List<Integer> result=new ArrayList<Integer>();
        int aIndex=a.length()-1;
        int bIndex=b.length()-1;
        addChar(result,a,aIndex,b,bIndex,0);
        if(result.size()==0){
            return "";
        }
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=result.size()-1;i>=0;i--){
            stringBuilder.append(result.get(i));
        }
        return stringBuilder.toString();
    }

    private static void addChar(List<Integer> result,String a, int aIndex,String b,int bIndex,int carry){
        if(aIndex<0&&bIndex<0){
            /** 都计算完了*/
            if(carry>0){
                result.add(carry);
            }

        }else if(aIndex<0){
            /** a计算完了*/
            int sum=getNum(b.charAt(bIndex))+carry;
            if(sum>=2){
               carry=1;
            }else{
                carry=0;
            }
            result.add(sum%2);
            addChar(result,a,aIndex,b,--bIndex,carry);
        }else if(bIndex<0){
            /** b计算完了*/
            int sum=getNum(a.charAt(aIndex))+carry;
            if(sum>=2){
                carry=1;
            }else{
                carry=0;
            }
            result.add(sum%2);
            addChar(result,a,--aIndex,b,bIndex,carry);
        }else{
            /** 都没计算完*/
            int sum=getNum(a.charAt(aIndex))+getNum(b.charAt(bIndex))+carry;
            if(sum>=2){
                carry=1;
            }else{
                carry=0;
            }
            result.add(sum%2);
            addChar(result,a,--aIndex,b,--bIndex,carry);
        }
    }

    private static int getNum(char c){
        if(c=='0'){
            return 0;
        }else {
            return 1;
        }
    }

    public static void main(String[] args){
        String result=addBinary("11","1");
        System.out.println(result);

        String result2=addBinary("1010","1011");
        System.out.println(result2);
    }
}
